package leetcode_周赛._2023._04;

import java.util.*;

/**
 * 第 339 场周赛
 * AC_2
 *
 * @author yezh
 * @date 2023/4/2 20:46
 */
public class _02 {

    /**
     * 转换二维数组
     * 算法: 哈希表
     * 统计每个数字的个数, 用哈希表存下来
     */
    public List<List<Integer>> findMatrix(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, Integer> cnts = new HashMap<>();
        for (int num : nums) cnts.put(num, cnts.getOrDefault(num, 0) + 1);
        while (!cnts.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : cnts.entrySet()) {
                list.add(entry.getKey());
                if (entry.getValue() - 1 == 0) cnts.remove(entry.getKey());
                else cnts.put(entry.getKey(), entry.getValue() - 1);
            }
            ans.add(list);
        }
        return ans;
    }

    /**
     * 老鼠和奶酪
     * 算法: 贪心
     */
    public int miceAndCheese(int[] reward1, int[] reward2, int k) {
        int ans = 0, n = reward1.length;
        // 都给第二只老鼠吃
        for (int reward : reward2) ans += reward;
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) diff[i] = reward1[i] - reward2[i];
        // 从 n 里面分出 k 块给第一只老鼠,
        // k 块是 reward1 与 reward2 差值最大的前 k 块, 这样就能保证结果是最大的
        // 从 diff 中找出前 k 大个数, 使用快速排序时间复杂度可以达到 O(n)
        Arrays.sort(diff);
        for (int i = n - 1; i >= n - k; i--) ans += diff[i];
        return ans;
    }

}
